package com.example.lettcode._202410._20241025._20241024;

import com.example.lettcode.node.ListNode;

import java.util.ArrayList;
import java.util.Deque;
import java.util.LinkedList;
import java.util.List;

/*
61. 旋转链表
给你一个链表的头节点 head ，旋转链表，将链表每个节点向右移动 k 个位置。

示例 1：
输入：head = [1,2,3,4,5], k = 2
输出：[4,5,1,2,3]

示例 2：
输入：head = [0,1,2], k = 4
输出：[2,0,1]
 */
public class _1_xuan_zhuan_lian_biao {

    public static void main(String[] args) {
        ListNode list1 = new ListNode(1);
        ListNode list2 = new ListNode(2);
        ListNode list3 = new ListNode(3);
        ListNode list4 = new ListNode(4);
        ListNode list5 = new ListNode(5);
        list1.next = list2;
        list2.next = list3;
        list3.next = list4;
        list4.next = list5;
        ListNode listNode = rotateRight2(list1, 2);
        System.out.println(listNode);
    }

    /*
        记录链表需要截断的位置前后节点，再重组
     */
    public static ListNode rotateRight2(ListNode head, int k) {
        if (head == null) {
            return head;
        }
        ListNode tempNode = head;
        Deque<ListNode> deque = new LinkedList<>();

        while (tempNode != null) {
            deque.push(tempNode);
            tempNode = tempNode.next;
        }
        k = k % deque.size();

        // 反转前的头节点
        ListNode oldHeadNode = head;
        // 反转前的尾节点
        ListNode oldLastNode = deque.getFirst();

        // 反转后的头结点
        ListNode newHeadNode = head;
        // 反转后的尾节点
        ListNode newLastNode = head;
        // 获取反转的节点
        for (int i = 0; i < k+1; i++) {
            if (i == k-1) {
                newHeadNode = deque.pop();
            } else if (i == k) {
                newLastNode = deque.pop();
            } else {
                deque.pop();
            }
        }

        ListNode retNode = newHeadNode;
        oldLastNode.next = oldHeadNode;
        newLastNode.next = null;
        return retNode;
    }


    /*
        将节点添加进list中，进行旋转后，再拼接
     */
    public static ListNode rotateRight(ListNode head, int k) {
        if (head == null) {
            return head;
        }
        ListNode node = head;
        List<ListNode> list = new ArrayList<>();
        while (node != null) {
            list.add(node);
            node = node.next;
        }
        k = k % list.size();
        reverseList(list);
        reverseList(list.subList(0, k));
        reverseList(list.subList(k, list.size()));
        ListNode newNode = new ListNode(-1);
        ListNode node2 = newNode;
        ListNode listNode = list.get(list.size() - 1);
        listNode.next = null;
        for (ListNode node3 : list) {
            node2.next = node3;
            node2 = node2.next;
        }
        return newNode.next;
    }

    /*
        怎么反转集合内的数组？
     */
    public static void reverseList(List<ListNode> list) {
        for (int i = 0; i < list.size()/2; i++) {
            ListNode tempNode = list.get(i);
            list.set(i, list.get(list.size() - 1 - i));
            list.set(list.size()-1-i, tempNode);
        }
    }
}
